package haffman;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class HuffmanTree {
    private int[] allData = {1,3,4,6,23,45,65,234};

    private LinkedList<Node> forest = new LinkedList<>();


    public Node createTree() {

        for (int i = 0; i <= allData.length -1; i++) {
            Node node = new Node(allData[i]);
            forest.add(node);
    }

        Node parent;
        Node left;
        Node right;
        while (forest.size() > 1) {
            left = forest.removeFirst();
            right = forest.removeFirst();
            parent = new Node(left.getData() + right.getData());
            parent.setLeft(left);
            parent.setRight(right);
            forest.add(getIndex(parent), parent);
        }
        return forest.getFirst();
    }

    public int getIndex(Node node) {
        for (int i = 0; i < forest.size(); i++) {
            if (node.getData() <= forest.get(i).getData()) {
                return i;
            }
        }
        return forest.size();
    }

    public void getNodeValue(Node node){
        if (node != null) {
            System.out.println(node.getData());
            getNodeValue(node.getLeft());
            getNodeValue(node.getRight());
        }
    }

    public void getHuffmanCode(Node node, String code) {
        if (node.getLeft() != null) {
            getHuffmanCode(node.getLeft(), code + "0");
        }
        if (node.getRight() != null) {
            getHuffmanCode(node.getRight(), code + "1");
        }
        if (node.getLeft() == null && node.getRight() == null) {
            System.out.println(code);
        }
    }

    public static void main(String[] args) {
        HuffmanTree huffmanTree = new HuffmanTree();
        Node node = huffmanTree.createTree();
        huffmanTree.getNodeValue(node);
        System.out.println("-----------------------");
        huffmanTree.getHuffmanCode(node, "");
    }
}
